package lc;
import util.*;
import java.util.*;

import org.junit.Test;

public class Ex297 {
    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "";
            Queue<TreeNode> queue = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            queue.offer(root);
            TreeNode cur;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (cur != null) {
                    sb.append(cur.val + "_");
                    //无论有没有，一视同仁
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                } else {
                    sb.append("#_");
                }
            }
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if ("".equals(data)) return null;
            String[] ss = data.split("_");
            TreeNode root = new TreeNode(Integer.parseInt(ss[0])), cur;
            int idx = 1;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (idx < ss.length) {
                String left = ss[idx++], right =  ss[idx++];
                cur = queue.poll();
                if (!"#".equals(left)) {
                    TreeNode t = new TreeNode(Integer.parseInt(left));
                    cur.left = t;
                    queue.offer(t);

                }
                if (!"#".equals(right)) {
                    TreeNode tt = new TreeNode(Integer.parseInt(right));
                    cur.right = tt;
                    queue.offer(tt);
                }
            }
            return root;
        }

}

    public class Codec2 {
            // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "";
            StringBuilder sb = new StringBuilder();
            pre1(root, sb);
            return sb.toString();
        }

        public void pre1(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("#_");
                return;
            }
            sb.append(root.val + "_");
            pre1(root.left, sb);
            pre1(root.right, sb);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if ("".equals(data)) return null;
            String[] ss = data.split("_");
            return pre2(ss);
        }
        int idx = 0;

        public TreeNode pre2(String[] ss) {
            if (idx == ss.length) {
                return null;
            }
            if (!"#".equals(ss[idx])) {
                TreeNode root = new TreeNode(Integer.parseInt(ss[idx]));
                idx++;
                root.left = pre2(ss);
                root.right = pre2(ss);
                return root;
            } 
            idx++;
            return null;
        }
    }

    @Test
    public void test() {
        Codec codec = new Codec();
        TreeNode root = TreeUtils.createTree(new Integer[]{1,2,3,null,null,4,5});
        String s = codec.serialize(root);
        System.out.println(s);
        TreeUtils.printBinaryTreeVisualization(codec.deserialize(s));
    }
    @Test
    public void test2() {
        Codec2 codec = new Codec2();
        TreeNode root = TreeUtils.createTree(new Integer[]{1,2,3,null,null,4,5});
        String s = codec.serialize(root);
        System.out.println(s);
        TreeUtils.printBinaryTreeVisualization(codec.deserialize(s));
    }
}
